package com.zlk.algorithm.dataStructure.tree.treeDp;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;


/**
 * @program: algorithm
 * @ClassName MaxHappy
 * @description:派对的最大快乐值
 * 员工信息的定义如下:
 * class Employee {
 *   public int happy; // 这名员工可以带来的快乐值
 *   List<Employee> subordinates; // 这名员工有哪些直接下级
 *  } 公司的每个员工都符合 Employee 类的描述。整个公司的人员结构可以看作是一棵标准的、 没有环的多叉树
 *  树的头节点是公司唯一的老板，除老板之外的每个员工都有唯一的直接上级
 *  叶节点是没有任何下属的基层员工(subordinates列表为空)，除基层员工外每个员工都有一个或多个直接下级
 *  这个公司现在要办party，你可以决定哪些员工来，哪些员工不来，规则：
 *  1.如果某个员工来了，那么这个员工的所有直接下级都不能来
 *  2.派对的整体快乐值是所有到场员工快乐值的累加
 *  3.你的目标是让派对的整体快乐值尽量大 给定一棵多叉树的头节点boss，请返回派对的最大快乐值。
 * @author: slfang
 * @create: 2024-02-21 19:35
 * @Version 1.0
 **/
public class MaxHappy {


    class Employee {
        public int happy; // 这名员工可以带来的快乐值
        List<Employee> nexts; // 这名员工有哪些直接下级
        public Employee(int h) {
            happy = h;
            nexts = new ArrayList<>();
        }

    }

    //可能性： 假设 boss 下有 a b c三个节点
    //     1、x 来   x.happy+ Max（a不来）+Max(b不来)+Max(c不来)
    //     2、x 不来  0+  Max（Max（a不来），Max(a来)）+Max（Max（b不来），Max(b来)）+Max（Max（c不来），Max(c来)）
    //信息  x来的值  x不来的值

    class Info{
        int is;
        int no;
        public Info(int is, int no) {
            this.is = is;
            this.no = no;
        }
    }


    public int maxHappy1(Employee employee){
        Info process = process(employee);
        return Math.max(process.is,process.no);
    }


    public Info process(Employee employee){
        if(employee==null){
            return new Info(0,0);
        }
        int is = employee.happy;
        int no = 0 ;
        for (Employee subordinate : employee.nexts) {
            Info info = process(subordinate);
            is +=info.no;
            no+=Math.max(info.is,info.no);
        }
        return new Info(is,no);
    }

    public int maxHappy2(Employee employee){
        if(employee == null){
            return 0;
        }
        return process2(employee,false);


    }

    private int process2(Employee employee, boolean up) {
        if(up){//上级来
            int ans = 0;
            for (Employee next : employee.nexts) {
                ans +=process2(next,false);
            }
            return ans;
        }else{//上级不来
            int happy = employee.happy;
            int no = 0;
            for (Employee next : employee.nexts) {
                happy+=process2(next,true);
                no+=process2(next,false);
            }
            return Math.max(happy,no);
        }
    }

    @Test
    public void test(){
        int maxLevel = 4;
        int maxNexts = 7;
        int maxHappy = 100;
        int testTimes = 100000;
        for (int i = 0; i < testTimes; i++) {
            Employee boss = genarateBoss(maxLevel, maxNexts, maxHappy);
            if (maxHappy1(boss) != maxHappy2(boss)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("finish!");
    }

    public  Employee genarateBoss(int maxLevel, int maxNexts, int maxHappy) {
        if (Math.random() < 0.02) {
            return null;
        }
        Employee boss = new Employee((int) (Math.random() * (maxHappy + 1)));
        genarateNexts(boss, 1, maxLevel, maxNexts, maxHappy);
        return boss;
    }

    // for test
    public  void genarateNexts(Employee e, int level, int maxLevel, int maxNexts, int maxHappy) {
        if (level > maxLevel) {
            return;
        }
        int nextsSize = (int) (Math.random() * (maxNexts + 1));
        for (int i = 0; i < nextsSize; i++) {
            Employee next = new Employee((int) (Math.random() * (maxHappy + 1)));
            e.nexts.add(next);
            genarateNexts(next, level + 1, maxLevel, maxNexts, maxHappy);
        }
    }
}
